package tree;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName AVLTree.java
 * @Description TODO
 * @createTime 2020年08月10日 20:36:00
 */
public class AvlTree<E extends TreeComparable> extends BaseBalanceTree<E> {

	public AvlTree() {
		this(null);
	}

	private static class AvlNode<E extends TreeComparable> extends Node<E> {
		private int height = 1;//默认为1.表示叶子节点

		public AvlNode(E element, Node<E> parent) {
			super(element, parent);
		}

		//计算平衡因子
		public int balanceFactor() {
			int leftHeight = left == null ? 0 : ((AvlNode<E>) left).height;
			int rightHeight = right == null ? 0 : ((AvlNode<E>) right).height;
			return Math.abs(leftHeight - rightHeight);
		}

		//更新高度，高度为左右子节点的最高的+1
		public void updateHeight() {
			int leftHeight = left == null ? 0 : ((AvlNode<E>) left).height;
			int rightHeight = right == null ? 0 : ((AvlNode<E>) right).height;
			height = 1 + Math.max(leftHeight, rightHeight);
		}

		public Node<E> tallerChild() {
			int leftHeight = left == null ? 0 : ((AvlNode<E>) left).height;
			int rightHeight = right == null ? 0 : ((AvlNode<E>) right).height;
			//如果左子树比右子树高，则返回左子树，进行旋转
			if (leftHeight > rightHeight) {
				return left;
			} else if (leftHeight == rightHeight) {
				return isLeftChild() ? left : right;
			} else {
				//如果右子树比左子树高，则返回右子树，进行旋转
				return right;
			}
		}
	}

	@Override
	public void updateHeight(Node<E> node) {
		((AvlNode<E>) node).updateHeight();
	}

	private boolean isBalance(Node<E> node) {
		int factor = ((AvlNode<E>) node).balanceFactor();
		return factor <= 1;
	}

	public AvlTree(TreeComparable<E> comparable) {
		super(comparable);
	}


	@Override
	protected Node<E> createNode(E element, Node<E> parent) {
		return new AvlNode<>(element, parent);
	}

	/**
	 * todo
	 *
	 * @param node 高度最低的不平衡节点
	 * @author songzihao
	 */
	@Override
	protected void balanceTree(Node<E> node) {
		//第一次进来的必定是叶子节点，然后一直查找父节点
		while ((node = node.parent) != null) {
			//node 是否平衡
			if (isBalance(node)) {
				//更新高度
				updateHeight(node);
			} else {
				//恢复平衡
				rebalance(node);
				break;
			}
		}
	}

	private void rebalance(Node<E> grandParentNode) {
		Node<E> parent = ((AvlNode<E>) grandParentNode).tallerChild();
		Node<E> node = ((AvlNode<E>) parent).tallerChild();
		if (parent.isLeftChild()) {//L
			if (node.isLeftChild()) {// LL
				rotateRight(parent);
			} else {// LR
				rotateLeft(parent);
				rotateRight(node);
			}
		} else {//R
			if (node.isLeftChild()) {// RL
				rotateRight(parent);
				rotateLeft(node);
			} else {// RR
				rotateLeft(parent);
			}
		}
	}

	protected void rebalanceWayTwo(Node<E> grandParentNode) {
		Node<E> parent = ((AvlTree.AvlNode<E>) grandParentNode).tallerChild();
		Node<E> node = ((AvlTree.AvlNode<E>) parent).tallerChild();
		if (parent.isLeftChild()) {//L
			if (node.isLeftChild()) {// LL

				rotate(grandParentNode,node.left,node,node.right,parent,parent.right,parent,parent.right);
			} else {// LR
				rotate(grandParentNode,parent.left,parent,node.left,node,node.right,grandParentNode,grandParentNode.right);
			}
		} else {//R
			if (node.isLeftChild()) {// RL
				rotate(grandParentNode,grandParentNode.left,grandParentNode,node.left,node,node.right,parent,parent.left);
			} else {// RR
				rotate(grandParentNode,grandParentNode.left,grandParentNode,parent.left,parent,node.left,node,node.right);
			}
		}
	}
	@Override
	protected void afterRemove(Node<E> node,Node<E> replacement) {
		//一直寻找到失衡的节点然后平衡
		while ((node = node.parent) != null) {
			//node 是否平衡
			if (isBalance(node)) {
				//更新高度
				updateHeight(node);
			} else {
				//恢复平衡
				rebalance(node);
				break;
			}
		}
	}
}
